package com.wj.algorithm.lintcode;


public class P182 {
    /*
     * 给出一个字符串 A, 表示一个 n 位正整数, 删除其中 k 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。
                    找到删除 k 个数字之后的最小正整数。
       N <= 240, k <= N
      
      
     * @param A: A positive integer which has N digits, A is a string
     * @param l: Remove k digits
     * @return: A string
     * 思路：要获取最小的数，那就是保证从高到底位都是在当前可选范围内最小的数字；
     * 
     * 长度为N的字符串，删掉l个，剩余N-1，几位x个
     * 
     * 那结果就是x位的数字
     * 从高位到地位依次生成每一位的数字，由于要求“使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数”
     * 那么，生成每一位，都应该从左往右遍历，每次都在可选范围获得最小的数字
     * 可选范围就是，获取第1位的数字是，要保证遍历的时候，不能使得当前遍历位置后面剩余的数字个数小于x-1即可
     */
    public String DeleteDigits(String a, int l) {
        // write your code here
        if(a == null || a.length() <= 0) {
            return "";
        }
        int len = a.length();
        if(l < 0 || l > len){
            return "";
        }
        
        String rs = "";
        
        //每次遍历记录最小数字的下标
        int numFromIndex = 0;
        int numMin = 10;//最小数字的值
        
        //新数字的位数
        int rsNum = len - l;
        
        //遍历获取rsNum个数字，终止条件就是全部获取
        for(int i = numFromIndex; rsNum > 0 && i < len ; i ++) {
            
            char ch = a.charAt(i);
            int currentValue = Integer.parseInt(ch + "");
            if(currentValue < numMin) {//比较，得到最小数字和下标
                numMin = currentValue;
                numFromIndex = i;
            }
            
            if(i >= len - rsNum) {//一轮结束，达到最大可选范围的边界
                i = numFromIndex;
                if(numMin > 0 || rs.length() > 0) {//处理首位为0的情况
                    rs += numMin;
                }
                numFromIndex = 0;
                numMin = 10;
                rsNum --;
                continue;
            }
        }
        
        return rs;
    }
    
    public static void main(String[] args) {
        System.out.println(new P182().DeleteDigits("178542", 4));
        System.out.println(new P182().DeleteDigits("87654321", 2));
        System.out.println(new P182().DeleteDigits("90249", 2));
        
    }
}
